1. Field of Invention
The concept of the invention relates to an improved complex multiplier for use in a simplified FFT butterfly arithmetic unit.
2. Description of the Prior Art
In the field of spectral analysis by digital machine means, and more particularly in sequency analyzers such as fast fourier transform devices, machine mechanizations of the algorithm to be solved have been quite complex and expensive, as to limit the applications of and markets for such machines. A key function in such mechanization is the multiplication of two complex values.
In the digital fast fourier processing of a sampled time history of say N samples over the sampled signal epoch of interest, successive samples are treated as complex quantities and are organized as two groups of sequences, each occurring in a mutually exclusive one of a first half and second half (A and B) of the sampled epoch. As is more fully explained in U.S. Pat. No. 4,158,888 to Shapiro for FAST FOURIER TRANSFORM PROCESSOR USING SERIAL PROCESSING AND DECODER ARITHMETIC AND CONTROL SECTION, the FFT processor may be characterized as a digital processor which repetitively performs the basic computations AW+B and AW-B, where A and B are complex digital words, each corresponding to a different one of N digital samples to be analyzed, and W is a complex digital word corresponding to a weighting function or "twiddle factor". Mechanization involves use of a multiplier to provide components of the complex product AW, storage means to store such product, and an adder/subtractor for combining such stored product to generate the complex product AW and to combine this complex product with the components of the complex variable B.
Detailed arithmetic processing of the sequential computations in a sequency analyzer or FFT machine, as a practical matter, involves reorganizing the discrete fourier transform data matrix into submatrices, each of which requires simpler arithmetic operations, and the results of which simpler operations may be merely simply combined, rather than multiplied. Such reorganization process is referred to generically as decimation, the two classical methods of reorganizing the data matrix being referred to as decimation-infrequency and decimation-in-time. The basic resultant computational operation is called a "butterfly".
A fuller discussion of the FFT "butterfly" arithmetic for both decimate-in-frequency and decimate-in-time applications, is provided in my co-pending Application Ser. No. 092,387 filed Nov. 8, 1979 for SIMPLIFIED FAST FOURIER TRANSFORM BUTTERFLY ARITHMETIC UNIT (now issued as U.S. Pat. No. 4,275,452). A yet more general discussion may be found in the text "Digital Signal Processing" by Peled and Liu, published by John Wiley and Sons, New York (1976). The above-noted co-pending patent application is directed to reducing the machine steps and arithmetic sequences involved in performing the bufferfly computation. Such reference discloses a simplified butterfly arithmetic unit employing a pair of registers for storing the respective sum and difference of the components, W.sub.R and W.sub.I, of the complex-butterfly twiddle factor, W, as phase-shifted cosine values. Controlled switching of two accumulators, responsive to alternate ones of the sum and difference registers, allows generation of the complex weighted butterfly output function, y=wz, without the necessity of discrete multipliers.
Such use of discrete multipliers has long been a source of machine complexity and limited machine speed. While the use of such discrete multipliers may be successfully avoided by means of my above-noted co-pending application, Ser. No. 092,387 (now U.S. Pat. No. 4,275,452), yet the use of discrete multipliers can be rendered less onerous by the use of a "lock-up table" type complex multiplier, employing square-function read-only memories (ROM's) in a quarter-square multiplier type configuration, in accordance with the inventive concept disclosed more fully hereinafter.